package leetcode.p1713;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author: trtan
 * @date: 2021-07-26 15:13
 **/
public class MinimumOperationsToMakeSubsequence {
    /**
     * 题目要求给arr任意位置添加任意数字，使得target为arr的子序列，
     * 由于target中所有数字均不同，那么给target中数字按下标换算
     * 对应换算arr中数字，arr中不在target中的数字不用换算直接删除，即得到一个新的arr序列arr`
     * arr`的最长上升子序列，长度一定是小于等于target的长度的
     * 最后答案即为target数组长度减去arr`最长上升子序列的长度
     * @param target
     * @param arr
     * @return int
     * @author trtan
     * @date 2021/7/26 15:13
     */
    public int minOperations(int[] target, int[] arr) {
        Map<Integer, Integer> map = new HashMap<>(16);
        for (int i = 0; i < target.length; i++) {
            map.put(target[i], i);
        }
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            int x = map.getOrDefault(arr[i], -1);
            if (x >= 0) {
                int size = list.size();
                if (size == 0 || x > list.get(size - 1)) {
                    list.add(x);
                } else {
                    int l = 0, r = size - 1, pos = size - 1;
                    while (l <= r) {
                        int mid = (l + r) / 2;
                        if (list.get(mid) >= x) {
                            r = mid - 1;
                            pos = mid;
                        } else {
                            l = mid + 1;
                        }
                    }
                    list.set(pos, x);
                }
            }
        }
        return target.length - list.size();
    }
}
